// ml:run = $bin < input
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;

int const up = 10000;

int main()
{
    std::ios_base::sync_with_stdio(false);
    int t;
    scanf("%d", &t);
    for(int tt=1;tt<=t;tt++)
    {
        int d, a, g1, g2, g3;
        scanf("%d%d%d%d%d", &d, &a, &g1, &g2, &g3);
        ll M=1LL<<50;
        M=min(M, (ll)(g2+a*g1+a*g3));
        ll v=sqrt((ll)((d-1)*a*g1/g2));
        ll vt=v;
        ll tmp=(d-1)/v;
        while(v>0&&abs((d-1)/v-tmp)<=1&&abs(v-vt)<=up){
            M=min(g2*v+((d-1)/v+1)*a*g1, M);
            v--;
        }
        v++;
        while(v>0&&abs((d-1)/v-tmp)<=1&&abs(v-vt)<=up){
            M=min(g2*v+((d-1)/v+1)*a*g1, M);
            v++;
        }
        printf("Case #%d: %lld\n", tt, M);
    }
}

